import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-15
 * Time: 9:15
 */
class Trie{
    public Map<Character, Trie> children;
    public int sum;  // 记录所有前缀中包含这个前缀的和
    public Trie(){
        this.children = new HashMap<>();
    }
}

public class MapSum {
    private Trie root;
    // 记录都已经存在哪些前缀了
    // 并且因为有 这个 map 了, 也不用结束标志了
    private HashMap<String, Integer> map;
    /** Initialize your data structure here. */
    public MapSum() {
        this.root = new Trie();
        this.map = new HashMap<>();
    }

    public void insert(String key, int val) {
        int oldValue = map.getOrDefault(key, 0);
        // 存在这个前缀, 并且前缀的值没有变, 就不用继续了
        if (oldValue == val){
            return;
        }
        // 找到差值, 修改整条路径上的值
        int sub = val - oldValue;
        Trie cur = root;
        for (Character c : key.toCharArray()){
            if (!cur.children.containsKey(c)){
                cur.children.put(c, new Trie());
            }
            cur = cur.children.get(c);
            cur.sum += sub;
        }
        // 添加到 map 中
        map.put(key, val);
    }

    /**
     *  求所有前缀中包含这个前缀的和
     * @param prefix
     * @return
     */
    public int sum(String prefix) {
        Trie cur = this.root;
        for (Character c : prefix.toCharArray()){
            if (!cur.children.containsKey(c)){
                return 0;
            }
            cur = cur.children.get(c);
        }
        return cur.sum;
    }
}
